package offer.offer13;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @Author: wjy
 * @Date: 2021/10/28 20:39
 */
public class Solution {

    public static void main(String[] args) {

        Solution solution = new Solution();
        System.out.println(solution.movingCount(16, 8, 4));



    }

    int count = 0;

    public int movingCount(int m, int n, int k) {

        int[][] ints = new int[m][n];

        this.result(0, 0, k, ints);

        return count;

    }

    public void result(int i, int j, int k, int[][] arr) {

        if (i == arr.length || j == arr[0].length || arr[i][j] == 1){
            return;
        }

        int x = 10, y = 1, sum = 0;

        while (true) {
            sum += (i % x) / y;
            sum += (j % x) / y;
            y = x;
            x *= 10;
            if (i % y == i && j % y == j) {
                break;
            }
        }

        if (sum <= k) {
            arr[i][j] = 1;
            count++;
            this.result(i, j+1, k, arr);
            this.result(i + 1, j, k, arr);
        }
    }

}
